// 二分查找的应用
#include <stdio.h>
#include <math.h>

/// @brief 二分查找算法
/// @param array 数组
/// @param length 数组长度
/// @param target 待查找数
/// @return 待查找数下标，未找到返回-1
int binarySearch(int array[], int length, int target)
{
	// 高低位下标指针
	int low = 0, high = length - 1, mid;
	while (low <= high)
	{
		mid = low + (high - low) / 2;
		if (array[mid] == target)
		{
			return mid;
		}
		if (target > array[mid])
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

/// @brief 在递增的长度为length的有序数组array中查找比给定数target小的但是下标最大的数，并返回其下标，不存在返回-1
/// @param array 数组
/// @param length 数组长度
/// @param target 给定数
/// @return
int lowerBound(int array[], int length, int target)
{
	// 高低下标指针
	int low = 0, high = length - 1, mid, result = -1;
	while (low <= high)
	{
		mid = low + (high - low) / 2;
		// 给定数小于或者等于中间数时，都是往前缩小继续查找，使high = mid - 1即可
		if (target <= array[mid])
		{
			high = mid - 1;
		}
		else
		{
			// 给定数大于中间数时，说明中间数就很可能是结果，先记下来然后继续查找最优解
			result = mid;
			low = mid + 1;
		}
	}
	return result;
}

/**
 * 方程求根：给定f(x)=x^3-5x^2+10x-80，求根
 * 提示：若|f(a)|<=10^-6，则可以把a视为f(x)的根
 * 思路：对f(x)求导易得f'(x)>0，说明f(x)单调递增，而f(0)=-80<0，f(10)=520>0，所以f(x)在[0, 10]内有且只有一个根，因此通过二分查找方式计算即可
 */

/// @brief 计算方程的值
/// @param x 代入值
/// @return 结果
double getValue(double x)
{
	return pow(x, 3) - 5 * pow(x, 2) + 10 * x - 80;
}

/// @brief 方程二分法求根
/// @return 方程的根
double getRoot()
{
	// 判定范围，y绝对值小于这个数则x为根
	double bound = pow(10, -6);
	// 大小范围指针以及x作为解、y表示值
	double small = 0, big = 10, x = small + (big - small) / 2, y = getValue(x);
	// 大于判定范围继续求解
	while (fabs(y) > bound)
	{
		// y大了说明x大了，向前缩小x查找范围
		if (y > 0)
		{
			big = x;
		}
		else
		{
			small = x;
		}
		// 重新查找并计算
		x = small + (big - small) / 2;
		y = getValue(x);
	}
	return x;
}

/// @brief 求整数的平方根，结果保留整数
/// @param x 输入数
/// @return x的平方根
int mySqrt(int x)
{
	// 分别表示最低最高估计值，中间值和结果
	int low = 0, high = x, mid, result;
	while (low <= high)
	{
		mid = low + (high - low) / 2;
		if ((long)mid * mid <= x)
		{
			// 记录结果
			result = mid;
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return result;
}

int main()
{
	printf("%d", mySqrt(3));
	return 0;
}